package algorithmlearn.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//拓扑排序
//使用Kahn 算法和DFS 深度优先搜索算法，来拓扑排序，找出位图中的依赖关系
public class TopologicalSort {

    //1. Kahn 算法 // 给每一个顶点 加上入度属性，从入度为0度顶点开始遍历
    public List<Integer> topoSortByKahn(Graph graph) {
        //保存拓扑排序结果
        List<Integer> path = new ArrayList<>();

        LinkedList<Integer>[] adj = graph.getAdj();
        int v = graph.getV();
        int[] inDegree = new int[v]; // 统计每个顶点的入度
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
                Integer w = adj[i].get(j); // i->w
                inDegree[w] ++;
            }
        }
        //构造入度为0 的顶点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < v; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }
        //遍历入度为0 的顶点
        while (!q.isEmpty()){
            Integer i = q.remove();
            path.add(i);
            System.out.print("->" + i);
            for (int j = 0; j < adj[i].size(); j++) {
                Integer k = adj[i].get(j);
                inDegree[k] --;
                if(inDegree[k] == 0){//若 k顶点入度 减小到0，加入队列，等待遍历
                    q.add(k);
                }
            }
        }
        System.out.println();
        return path;
    }

    //2. 深度优先搜索（DFS）
    public void topoSortByDFS(Graph graph) {

        LinkedList<Integer>[] adj = graph.getAdj();
        int v = graph.getV();
        //记录每个顶点的逆邻接表：先构建逆邻接表，边 s->t 表示，s 依赖于 t，t 先于 s
        LinkedList<Integer>[] inversAdj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            inversAdj[i] = new LinkedList<>();
        }
        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) { // 通过邻接表生成逆邻接表
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j); // i->w
                inversAdj[w].add(i); // w->i
            }
        }

        for (int i = 0; i < v; i++) {// 深度优先遍历图
            if (!visited[i]) {
                visited[i] = true;
                dfs(i,inversAdj,visited);
            }

        }
    }

    private void dfs(Integer vertex, LinkedList<Integer>[] inverseAdj,boolean[] visited){
        for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
            int w = inverseAdj[vertex].get(i);
            if (visited[w] == true) continue;
            visited[w] = true;
            dfs(w, inverseAdj, visited);
        } // 先把 vertex 这个顶点可达的所有顶点都打印出来之后，再打印它自己
        System.out.print("->" + vertex);
    }


    public static void main(String[] args) {
        Graph graph = new Graph(7);
        graph.addEdg(0,1);
        graph.addEdg(1,2);
        graph.addEdg(3,4);
        graph.addEdg(4,5);
        graph.addEdg(5,6);
        System.out.println("TopologicalSort >>> -------");
        TopologicalSort topologicalSort = new TopologicalSort();
        List<Integer> path = topologicalSort.topoSortByKahn(graph);
        System.out.println("path >>> " + path);

        System.out.println("topoSortByDFS >>> -------");
//        List<Integer> path2 =
                topologicalSort.topoSortByDFS(graph);
//        System.out.println("path2 >>> " + path2);
    }
}

//位图
class Graph {
    private int v;
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdg(int s, int t) {
        adj[s].add(t);
    }

    public int getV() {
        return v;
    }

    public LinkedList<Integer>[] getAdj() {
        return adj;
    }
}